On the Construction of Data Aggregation Tree with Minimum Energy Cost in Wireless Sensor Networks: NP-Completeness and Approximation Algorithms

摘要

In many applications, it is a basic operation for the sink to periodicallycollect reports from all sensors. Since the data gathering process usuallyproceeds for many rounds, it is important to collect these data efficiently,that is, to reduce the energy cost of data transmission. Under suchapplications, a tree is usually adopted as the routing structure to save thecomputation costs for maintaining the routing tables of sensors. In this paper,we work on the problem of constructing a data aggregation tree that minimizesthe total energy cost of data transmission in a wireless sensor network. Inaddition, we also address such a problem in the wireless sensor network whererelay nodes exist. We show these two problems are NP-complete, and proposeO(1)-approximation algorithms for each of them. Simulations show that theproposed algorithms each have good performance in terms of the energy cost.